package org.syntaxlisp.core;

import org.syntaxlisp.core.element.*;
import org.syntaxlisp.core.utils.Pair;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Getter;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.StringUtils;

import java.lang.reflect.InvocationTargetException;
import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;

import static org.syntaxlisp.core.element.SyntaxLispElementType.isNoTerminalType;
import static org.syntaxlisp.core.utils.CommonUtils.checkOrThrow;
import static org.syntaxlisp.core.utils.CommonUtils.singletonList;
import static org.syntaxlisp.core.element.ReservedTag.*;

public class SyntaxLispParser {

    public static final int MAX_UNICODE_CODE_POINT = 65535;

    private SyntaxLispParser () { }

    public static void eliminatePureRef (Map<String, SyntaxLispElement> env) {
        AtomicBoolean isChange = new AtomicBoolean();
        do {
            isChange.set(false);
            env.forEach((defName, element) -> env.put(defName, eliminatePureRef0(element, env, isChange)));
        } while (isChange.get());
        env.entrySet()
           .removeIf(stringSyntaxLispElementEntry
                             -> SyntaxLispElementType.REF == stringSyntaxLispElementEntry.getValue().getType());
    }

    public static SyntaxLispElement eliminatePureRef0 (SyntaxLispElement cur,
                                                       Map<String, SyntaxLispElement> env,
                                                       AtomicBoolean isChange) {
        if (SyntaxLispElementType.isNoTerminalType(cur.getType())) {
            for (int i = 0; i < cur.getSubsSize(); i ++) {
                cur.setSub(i, eliminatePureRef0(cur.getSub(i), env, isChange));
            }
            if (SyntaxLispElementType.ALTERNATIVE == cur.getType()) {
                boolean isMerge = true;
                for (int i = 0; i < cur.getSubsSize() - 1; i ++) {
                    if (SyntaxLispElementType.REF != cur.getSub(i).getType()
                            || cur.getSub(i).getType() != cur.getSub(i + 1).getType()
                            || !cur.getSub(i).getVal().equals(cur.getSub(i + 1).getVal())) {
                        isMerge = false;
                        break;
                    }
                }
                if (isMerge) {
                    isChange.set(true);
                }
                return isMerge ? cur.getSub(0) : cur;
            }
        } else {
            if (SyntaxLispElementType.REF == cur.getType()) {
                String trimDefName = trimReference((ReferenceElement) cur, env).getDefName();
                if (!trimDefName.equals(cur.getVal())) {
                    isChange.set(true);
                    return new ReferenceElement(trimDefName);
                }
                return cur;
            }
        }
        return cur;
    }

    public static Pair<Map<String, SyntaxLispElement>, Collection<String>>
    parse(List<Element> rawLispElements, Collection<String> keptDefSet) {

        Map<String, SyntaxLispElement> env = new HashMap<>();
        Set<String> inclusiveDefSet = new HashSet<>();
        Set<String> refs = new HashSet<>();
        Map<String, Set<String>> defRefsMap = new HashMap<>();
        for (Element element : rawLispElements) {

            checkOrThrow(ElementType.LIST == element.getElementType(),
                         "首级 Expression 应为 List Expression");
            checkOrThrow(element.getSubSize() == 3, "DEFINITION 只支持 3 个参数");

            Element tagEle = element.getSub(0);
            ReservedTag defTag
                    = ReservedTag.matches(tagEle.getValue())
                                 .orElseThrow(() -> new ParseException("无法识别这个 List Tag: " + tagEle.getValue()));
            checkOrThrow(DEFINITION == defTag
                         || DEFINITION_INCLUSIVE == defTag
                         || DEFINITION_STRING == defTag,
                         "首级 Expression 应为 DEFINITION 或 DEFINITION_INCLUSIVE 或 DEFINITION_STRING");

            Set<String> collectRefs = new HashSet<>();
            String defName = element.getSub(1).getValue();
            checkOrThrow(SyntaxLispParseUtils.checkIsValidId(defName),
                         "DEFINITION 第 2 个参数为引用名称但实际为：" + defName);
            checkOrThrow(!env.containsKey(defName), "多次定义 " + defName);

            env.put(defName, parse0(element.getSub(2), collectRefs));
            defRefsMap.put(defName, collectRefs);
            refs.addAll(collectRefs);
            if (defTag == DEFINITION_INCLUSIVE) {
                inclusiveDefSet.add(defName);
            } else if (defTag == DEFINITION_STRING) {
                env.get(defName).setReduceAsString(true);
            }
        }
        // env 加入 Base Definitions
        Collection<String> bases = CollectionUtils.subtract(refs, env.keySet());
/*        for (String base : bases) {
            env.put(base, new BaseElement(base));
        }*/
        replaceBaseRef(env, bases);

        env.forEach((def, body) -> replaceBase(body, bases));
        keepChosenDef(env, defRefsMap, keptDefSet);
        replaceInclusiveRef (env, defRefsMap, inclusiveDefSet);
        inferAmbiguousDefType(env);
        env.forEach((defName, element) -> inferAndCheckType(element, env));
        reduceScope(env);
        parseToSimplifyRepeat(env);
        determineElementLayer(env);
        return Pair.<Map<String, SyntaxLispElement>, Collection<String>>builder()
                .first(env)
                .second(bases)
                .build();
    }

    private static void replaceBaseRef (Map<String, SyntaxLispElement> env, Collection<String> bases) {
        Map<String, SyntaxLispElement> replacedEnv = new HashMap<>(env.size());
        env.forEach((def, body) -> replacedEnv.put(def, replaceBaseRef(body, bases)));
        env.putAll(replacedEnv);
    }

    private static SyntaxLispElement replaceBaseRef (SyntaxLispElement cur, Collection<String> bases) {
        if (SyntaxLispElementType.isNoTerminalType(cur)) {
            for (int i = 0; i < cur.getSubsSize(); i ++) {
                cur.setSub(i, replaceBaseRef(cur.getSub(i), bases));
            }
            return cur;
        } else {
            return (SyntaxLispElementType.REF.isTypeMatch(cur)
                        && bases.contains(cur.getVal()))
                   ? new BaseElement(cur.getVal())
                   : cur;
        }
    }

    public static void determineElementLayer (Map<String, SyntaxLispElement> env) {
        env.forEach((def, body) -> setElementLayer(body, 0));
    }

    private static void setElementLayer (SyntaxLispElement cur, int layer) {
        cur.setLayer(layer);
        if (!CollectionUtils.isEmpty(cur.getSubElements())) {
            cur.getSubElements().forEach(sub -> setElementLayer(sub, layer + 1));
        }
    }

    public static SyntaxLispElement replaceBase (SyntaxLispElement cur, Collection<String> bases) {
        if (SyntaxLispElementType.REF.isTypeMatch(cur)) {
            if (bases.contains(cur.getVal())) {
                return new BaseElement(cur.getVal());
            }
        } else {
            if (!CollectionUtils.isEmpty(cur.getSubElements())) {
                for (int i = 0; i < cur.getSubsSize(); i++) {
                    cur.setSub(i, replaceBase(cur.getSub(i), bases));
                }
            }
        }
        return cur;
    }

    public static void replaceInclusiveRef (Map<String, SyntaxLispElement> env,
                                            Map<String, Set<String>> defRefsMap,
                                            Set<String> inclusiveDefSet) {
        // 校验 inclusiveDefSet 循环引用
        for (String inclusiveDef : inclusiveDefSet) {
            List<String> checkRefPath = new ArrayList<>();
            if (existInclusiveRefCycle(inclusiveDef, checkRefPath, defRefsMap, inclusiveDefSet)) {
                throw new ParseException("DEFINITION_INCLUSIVE 存在引用环路: " + checkRefPath);
            }
        }
        Iterator<Map.Entry<String, SyntaxLispElement>> i = env.entrySet().iterator();
        while (i.hasNext()) {
            Map.Entry<String, SyntaxLispElement> cur = i.next();
            String defName = cur.getKey();
            if (inclusiveDefSet.contains(defName)) {
//                List<ReferenceElement> refs = trimRefs(cur.getValue());
                env.forEach((rpDef, ele) -> {
                    if (!rpDef.equals(defName)) {
                        env.put(rpDef, replaceInclusiveRef(ele, defName, env));
                    }
                });
                i.remove();
            }
        }
    }

    public static SyntaxLispElement replaceInclusiveRef (SyntaxLispElement cur,
                                                         String replaceRef,
                                                         Map<String, SyntaxLispElement> env) {
        if (SyntaxLispElementType.REF.isTypeMatch(cur)
                && replaceRef.equals(cur.getVal())) {
            return env.get(replaceRef).copy();
        } else {
            if (SyntaxLispElementType.isNoTerminalType(cur)) {
                for (int i = 0; i < cur.getSubsSize(); i ++) {
                    cur.setSub(i, replaceInclusiveRef(cur.getSub(i), replaceRef, env));
                }
                if (SyntaxLispElementType.AMBIGUOUS_OR.isTypeMatch(cur)) {
                    return determineTypeWithSubs(cur.getSubElements());
                }
            }
            return cur;
        }
    }

    private static List<ReferenceElement> trimRefs (SyntaxLispElement cur) {
        if (SyntaxLispElementType.isNoTerminalType(cur)) {
            if (SyntaxLispElementType.AMBIGUOUS_OR.isTypeMatch(cur)) {
                return ((AmbiguousOrElement) cur).getRefs();
            } else {
                List<ReferenceElement> res = new ArrayList<>();
                cur.getSubElements().stream().forEach(sub -> res.addAll(trimRefs(sub)));
                return res;
            }
        } else {
            return SyntaxLispElementType.REF.isTypeMatch(cur)
                   ? Collections.singletonList((ReferenceElement) cur)
                   : Collections.emptyList();
        }
    }

    private static boolean existInclusiveRefCycle(String curDef,
                                                  List<String> refPath,
                                                  Map<String, Set<String>> defRefsMap,
                                                  Set<String> inclusiveDefSet) {
        if (refPath.contains(curDef)) {
            return true;
        } else {
            if (inclusiveDefSet.contains(curDef)) {
                refPath.add(curDef);
                for (String ref : defRefsMap.get(curDef)) {
                    if (existInclusiveRefCycle(ref, refPath, defRefsMap, inclusiveDefSet)) {
                        return true;
                    }
                }
                refPath.remove(curDef);
            }
            return false;
        }
    }

    public static void parseToSimplifyRepeat(Map<String, SyntaxLispElement> env) {
        env.forEach((def, ele) -> env.put(def, parseToSimplifyRepeat(ele)));
    }

    private static SyntaxLispElement parseToSimplifyRepeat(SyntaxLispElement cur) {
        if (isNoTerminalType(cur)) {
            switch (cur.getType()) {
                case NOT_OR: {
                    cur.setSub(0, parseToSimplifyRepeat(cur.getSub(0)));
                    break;
                }
                case REPEAT_GREEDY:
                case ZERO_OR_ONE_GREEDY:
                case ZERO_OR_MORE_GREEDY:
                case ONE_OR_MORE_GREEDY:
                case ZERO_OR_ONE:
                case ZERO_OR_MORE:
                case ONE_OR_MORE:
                case REPEAT: {
                    SimplifyRepeatElement parsed = new SimplifyRepeatElement(cur);
                    parsed.setRepeatBody(parseToSimplifyRepeat(parsed.getRepeatBody()));
                    return parsed.copyMatchPropertiesAndReturn(cur);
                }
                default: {
                    for (int i = 0; i < cur.getSubsSize(); i ++) {
                        cur.setSub(i, parseToSimplifyRepeat(cur.getSub(i)));
                    }
                }
            }
        }
        return cur;
    }

    /**
     * 保留选择的 entry def 以及其引用的 def，并将此之外的 def 从 env 中移除
     * @param env env
     * @param defRefsMap def 引用表
     * @param keptDefSet 需要保留的 entry def 集合
     */
    public static void keepChosenDef (Map<String, SyntaxLispElement> env,
                                      Map<String, Set<String>> defRefsMap,
                                      Collection<String> keptDefSet) {
        if (!CollectionUtils.isEmpty(keptDefSet)) {
            Set<String> refClojure = new HashSet<>();
            CollectionUtils.intersection(keptDefSet, env.keySet())
                           .forEach(def -> getRefClosure(def, defRefsMap, refClojure));
            for (String removedDef : CollectionUtils.subtract(env.keySet(), refClojure)) {
                env.remove(removedDef);
            }
        }
    }

    public static void getRefClosure (String curDef, Map<String, Set<String>> defRefsMap, Set<String> refClojure) {
        if (!refClojure.contains(curDef)) {
            refClojure.add(curDef);
            for (String ref : defRefsMap.getOrDefault(curDef, Collections.emptySet())) {
                getRefClosure(ref, defRefsMap, refClojure);
            }
        }
    }

    public static List<SyntaxLispElement> parse0List(List<Element> rawElements, Set<String> collectRefs) {
        List<SyntaxLispElement> res = new ArrayList<>(rawElements.size());
        rawElements.forEach(element -> res.add(parse0(element, collectRefs)));
        return res;
    }

    public static List<SyntaxLispElement> reduce0List(List<SyntaxLispElement> rawElements,
                                                      Map<String, SyntaxLispElement> env,
                                                      Queue<String> reduceStack) {
        List<SyntaxLispElement> res = new ArrayList<>(rawElements.size());
        rawElements.forEach(element -> res.add(reduceScope0(element, env, reduceStack)));
        return res;
    }


    public static SyntaxLispElement parse0(Element rawElement, Set<String> collectRefs) {
        if (ElementType.LIST == rawElement.getElementType()) {
            List<Element> subElements = rawElement.getSubItems();
            checkOrThrow(!CollectionUtils.isEmpty(subElements), "LIST 至少需要一个参数");
            Element tagEle = subElements.get(0);
            checkOrThrow(ElementType.TOKEN == tagEle.getElementType(), "LIST 首部应为 Function Tag");
            ReservedTag tag
                    = ReservedTag.matches(tagEle.getValue())
                                 .orElseThrow(() -> new ParseException("无法识别这个 List Tag: " + tagEle.getValue()));
            switch (tag) {
                case SCOPE: {
                    checkOrThrow(subElements.size() == 3, "SCOPE 只支持 2 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.SCOPE,
                                                     parse0List(subElements.subList(1, subElements.size()), 
                                                                collectRefs));
                }
                case UNICODE_CHARACTER: {
                    checkOrThrow(subElements.size() == 2, "UNICODE 只支持 1 个 HEX DIGIT 参数.");
                    Element hexDigitEle = subElements.get(1);
                    int codePoint = parseHexDigit(hexDigitEle);
                    checkOrThrow(codePoint <= MAX_UNICODE_CODE_POINT,
                                 "超出所支持的 Unicode code point 范围");
                    return new CharacterElement(hexDigitEle.getValue(), codePoint);
                }
                case NOT_IN: {
                    checkOrThrow(subElements.size() > 2, "NOT_IN 至少需要 2 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.SUBTRACT_SCOPE,
                                                     parse0List(subElements.subList(1, subElements.size()), 
                                                                collectRefs));
                }
                case REPEAT_GREEDY: {
                    checkOrThrow(subElements.size() == 4, "REPEAT_GREEDY 只支持 3 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.REPEAT_GREEDY,
                                                     parse0List(subElements.subList(1, subElements.size()),
                                                                collectRefs));
                }
                case REPEAT: {
                    checkOrThrow(subElements.size() == 4, "REPEAT 只支持 3 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.REPEAT,
                                                     parse0List(subElements.subList(1, subElements.size()), 
                                                                collectRefs));
                }
                case ALTERNATIVE: {
                    checkOrThrow(subElements.size() > 2, "OR 至少需要 2 个参数.");
                    List<SyntaxLispElement> parsedSubElements = parse0List(subElements.subList(1, subElements.size()),
                                                                           collectRefs);
                    return determineTypeWithSubs(parsedSubElements);
                }
                case ZERO_OR_MORE_GREEDY: {
                    checkOrThrow(subElements.size() == 2, "ZERO_OR_MORE_GREEDY 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ZERO_OR_MORE_GREEDY,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case ZERO_OR_MORE: {
                    checkOrThrow(subElements.size() == 2, "ZERO_OR_MORE 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ZERO_OR_MORE,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case ZERO_OR_ONE_GREEDY: {
                    checkOrThrow(subElements.size() == 2, "ZERO_OR_ONE_GREEDY 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ZERO_OR_ONE_GREEDY,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case ZERO_OR_ONE: {
                    checkOrThrow(subElements.size() == 2, "ZERO_OR_ONE 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ZERO_OR_ONE,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case ONE_OR_MORE_GREEDY: {
                    checkOrThrow(subElements.size() == 2, "ONE_OR_MORE_GREEDY 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ONE_OR_MORE_GREEDY,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case ONE_OR_MORE: {
                    checkOrThrow(subElements.size() == 2, "ONE_OR_MORE 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.ONE_OR_MORE,
                                                     singletonList(parse0(subElements.get(1), collectRefs)));
                }
                case SEQ_CONNECT: {
                    checkOrThrow(subElements.size() > 2, "SEQ_CONNECT 至少需要 2 个参数.");
/*                    // 合并相连的 string
                    List<Element> unParsedSubElements = subElements.subList(1, subElements.size());
                    List<SyntaxLispElement> res = new ArrayList<>(unParsedSubElements.size());
                    String prevStringVal = null;
                    for (Element subElement : unParsedSubElements) {
                        SyntaxLispElement parsedSub = parse0(subElement, collectRefs);
                        if (SyntaxLispElementType.STRING.isTypeMatch(parsedSub)
                            || SyntaxLispElementType.CHARACTER.isTypeMatch(parsedSub)) {
                            prevStringVal = (prevStringVal != null) ? (prevStringVal + parsedSub.getVal())
                                                                    : parsedSub.getVal();
                        } else {
                            if (prevStringVal != null) {
                                res.add(new StringElement(prevStringVal));
                                prevStringVal = null;
                            }
                            res.add(parsedSub);
                        }
                    }
                    // 收尾
                    if (prevStringVal != null) {
                        res.add(new StringElement(prevStringVal));
                    }
                    return new ListExpressionElement(SyntaxLispElementType.SEQ_CONNECT, res);*/
                    return new ListExpressionElement(SyntaxLispElementType.SEQ_CONNECT,
                                                     parse0List(subElements.subList(1, subElements.size()), collectRefs));
                }
                case NOT_OR: {
                    checkOrThrow(subElements.size() > 2, "NOT_OR 至少需要 2 个参数.");
                    return new NotOrElement(parse0List(subElements.subList(1, subElements.size()), collectRefs));
                }
                case IMPORT: {
                    checkOrThrow(subElements.size() == 2, "IMPORT 只接受 1 个参数.");
                    return new ListExpressionElement(SyntaxLispElementType.IMP,
                                                     parse0List(subElements.subList(1, subElements.size()), collectRefs));
                }
                case HUNGER: {
                    checkOrThrow(subElements.size() == 2, "HUNGER 只接受 1 个参数.");
                    SyntaxLispElement parsedBody = parse0(subElements.get(1), collectRefs);
                    parsedBody.setHunger(true);
                    return parsedBody;
                }
                case LOOK_AHEAD_EXCLUDE: {
                    checkOrThrow(subElements.size() > 2, "LOOK_AHEAD_EXCLUDE 至少需要 2 个参数.");
                    List<SyntaxLispElement> parsedSubs = parse0List(subElements.subList(1, subElements.size()),
                                                                    collectRefs);
                    for (int i = 1; i < parsedSubs.size(); i ++) {
                        checkOrThrow(SyntaxLispElementType.STRING.isTypeMatch(parsedSubs.get(i))
                                        || SyntaxLispElementType.CHARACTER.isTypeMatch(parsedSubs.get(i)),
                                     "LOOK_AHEAD_EXCLUDE exclude params 只接受 STRING 或 CHARACTER 类型.");
                    }
                    parsedSubs.get(0).setLookAheadExcludes(new HashSet<>(parsedSubs.subList(1, parsedSubs.size())));
                    return parsedSubs.get(0);
                }
                case MATCH_BUT_IGNORE: {
                    checkOrThrow(subElements.size() == 2, "MATCH_BUT_IGNORE 只接受 1 个参数.");
                    SyntaxLispElement parsedBody = parse0(subElements.get(1), collectRefs);
                    parsedBody.setMatchButIgnore(true);
                    return parsedBody;
                }
                default: {
                    throw new ParseException("Unexpected tag:" + tag);
                }
            }
        } else if (ElementType.STRING == rawElement.getElementType()) {
            return rawElement.getValue().length() == 1
                    ? new CharacterElement(rawElement.getValue(), parseCodePointFromString(rawElement))
                    : new StringElement(rawElement.getValue());
        } else {
            // Parse Type Value
            String rawVal = rawElement.getValue();
            if (ReservedTag.UNICODE_CHARACTER_SCOPE.isMatch(rawVal)) {
                List<SyntaxLispElement> chs = new ArrayList<>(2);
                chs.add(new CharacterElement("\u0000", 0));
                chs.add(new CharacterElement("\uFFFF", MAX_UNICODE_CODE_POINT));
                return new ListExpressionElement(SyntaxLispElementType.SCOPE, chs);
            } else if (ReservedTag.INFINITY.isMatch(rawVal)) {
                return new NumberElement(0, true);
            } else {
                if (SyntaxLispParseUtils.isLetter(rawVal.charAt(0))) {
                    checkOrThrow(SyntaxLispParseUtils.checkIsValidId(rawVal), "遇到不合法的Id");
                    collectRefs.add(rawVal);
                    return new ReferenceElement(rawVal);
                } else if (SyntaxLispParseUtils.isDigit(rawVal.charAt(0))) {
                    return new NumberElement(parseNumber(rawElement), false);
                } else {
                    throw new ParseException(rawVal);
                }
            }
        }
    }

    private static SyntaxLispElement determineTypeWithSubs (List<SyntaxLispElement> parsedSubElements) {
        List<ReferenceElement> refs = new ArrayList<>();
        int notCount = 0;
        for (SyntaxLispElement element : parsedSubElements) {
            switch (element.getType()) {
                case SCOPE:
                case CHARACTER: break;
                case AMBIGUOUS_OR: refs.addAll(((AmbiguousOrElement) element).getRefs()); break;
                case REF: refs.add((ReferenceElement) element); break;
                default: notCount += 1;
            }
        }
        if (notCount > 0) {
            return new ListExpressionElement(SyntaxLispElementType.ALTERNATIVE, parsedSubElements);
        } else if (!refs.isEmpty()) {
            return new AmbiguousOrElement(refs, parsedSubElements);
        } else {
            return new ListExpressionElement(SyntaxLispElementType.UNION_SCOPE, parsedSubElements);
        }
    }

    private static void reduceScope (Map<String, SyntaxLispElement> env) {
        env.forEach((defName, element) -> {
            Queue<String> reduceStack = new ArrayDeque<>();
            reduceStack.offer(defName);
            env.put(defName, reduceScope0(element, env, reduceStack));
        });
    }

    private static SyntaxLispElement reduceScope0 (SyntaxLispElement cur,
                                                   Map<String, SyntaxLispElement> env,
                                                   Queue<String> reduceStack) {

        if (cur instanceof CharacterScope) { return cur; }

        switch (cur.getType()) {
            case SCOPE: {
                CharacterElement start = (CharacterElement) reduceScope0(cur.getSub(0), env, reduceStack);
                CharacterElement end = (CharacterElement) reduceScope0(cur.getSub(1), env, reduceStack);
                return (new MapScopeElement(start.getCodepoint(), end.getCodepoint(), MAX_UNICODE_CODE_POINT))
                        .copyMatchPropertiesAndReturn(cur);
            }
            case SUBTRACT_SCOPE: {
                SyntaxLispElement srcScope = reduceScope0(cur.getSub(0), env, reduceStack);
                MapScopeElement target = new MapScopeElement((CharacterScope) srcScope);
                for (int i = 1; i < cur.getSubElements().size(); i ++) {
                    SyntaxLispElement removeScope = reduceScope0(cur.getSub(i), env, reduceStack);
                    if (SyntaxLispElementType.CHARACTER == removeScope.getType()) {
                        target.remove(((CharacterElement) removeScope).getCodepoint());
                    } else {
                        target.remove((CharacterScope) removeScope);
                    }
                }
                return target.copyMatchPropertiesAndReturn(cur);
            }
            case UNION_SCOPE: {
                return (new MapScopeElement(reduce0List(cur.getSubElements(), env, reduceStack), MAX_UNICODE_CODE_POINT))
                        .copyMatchPropertiesAndReturn(cur);
            }
            case IMP: {
                String importScopeClazzName = cur.getSub(0).getVal();
                try {
                    Class<?> importScopeClazz = Class.forName(importScopeClazzName);
                    checkOrThrow(CharacterScope.class.isAssignableFrom(importScopeClazz),
                                 "IMPORT scope class MUST implements "
                                 + "com.syntaxlisp.element.CharacterScope");
                    return (new MapScopeElement((CharacterScope) importScopeClazz.getDeclaredConstructor()
                                                                                 .newInstance()))
                            .copyMatchPropertiesAndReturn(cur);
                } catch (ClassNotFoundException e) {
                    throw new ParseException("IMPORT scope class " + importScopeClazzName + " not found!");
                } catch (InstantiationException | IllegalAccessException | InvocationTargetException e) {
                    throw new ParseException("Exception happened when get instance of IMPORT scope class "
                                                     + importScopeClazzName + ": " + e);
                } catch (NoSuchMethodException e) {
                    throw new ParseException("Can not find a no-argument constructor method of "
                                                     + importScopeClazzName + ": " + e);
                }
            }
            case CHARACTER: { return cur; }
            case REF: {
                ReferencePair target = trimReference((ReferenceElement) cur, env);
                checkOrThrow(!reduceStack.contains(target.getDefName()), "SCOPE Reduce Cycle: " + reduceStack);
                reduceStack.offer(target.getDefName());
                SyntaxLispElement reduceRes = reduceScope0(target.getElement(), env, reduceStack);
                reduceStack.poll();
                return SyntaxLispElementType.SCOPE == reduceRes.getType()
                        ? reduceRes
                        : cur;
            }
            default: {
                if (SyntaxLispElementType.isNoTerminalType(cur)) {
                    for (int i = 0; i < cur.getSubsSize(); i ++) {
                        SyntaxLispElement curSub = cur.getSub(i);
                        if (SyntaxLispElementType.REF != curSub.getType()) {
                            cur.setSub(i, reduceScope0(curSub, env, new ArrayDeque<>()));
                        }
                    }
                }
                return cur;
            }
        }
    }

    /**
     * Define类型推断
     * @param env
     */
    private static void inferAmbiguousDefType(Map<String, SyntaxLispElement> env) {
        Map<String, List<String>> ambiguousDefMap = new HashMap<>(env.size());
        env.forEach((name, element) -> {
            if (SyntaxLispElementType.AMBIGUOUS_OR == element.getType()) {
                List<String> refs = new ArrayList<>();
                for (ReferenceElement refElement : ((AmbiguousOrElement) element).getRefs()) {
                    refs.add(trimReference(refElement, env).getDefName());
                }
                ambiguousDefMap.put(name, refs);
            }
        });
        int prevSize;
        do {
            prevSize = ambiguousDefMap.size();
            Iterator<Map.Entry<String, List<String>>> i = ambiguousDefMap.entrySet().iterator();
            while (i.hasNext()) {
                Map.Entry<String, List<String>> cur = i.next();
                String defName = cur.getKey();
                List<String> refs = cur.getValue();
                boolean allScope = true;
                boolean noScAr = false;
                for (String refName : refs) {
                    SyntaxLispElementType targetType = inferType(env.get(refName), env);
                    if (SyntaxLispElementType.CHARACTER != targetType
                            && !isScopeType(targetType)) {
                        allScope = false;
                        noScAr = SyntaxLispElementType.AMBIGUOUS_OR != targetType;
                        break;
                    }
                }
                if (allScope || noScAr) {
                    SyntaxLispElement srcElement = env.get(defName);
                    ListExpressionElement target = new ListExpressionElement(allScope
                                                                             ? SyntaxLispElementType.UNION_SCOPE
                                                                             : SyntaxLispElementType.ALTERNATIVE,
                                                                             srcElement.getSubElements());
                    env.put(defName, target.copyMatchPropertiesAndReturn(srcElement));
                    i.remove();
                }
            }
        } while (prevSize > ambiguousDefMap.size());

        if (!ambiguousDefMap.isEmpty()) {
            throw new ParseException("存在无法推断类型的引用环路：" + ambiguousDefMap);
        }
    }

    /**
     * 对 element 进行参数类型推断以及校验
     * @param cur
     * @param env
     * @return
     */
    private static SyntaxLispElement inferAndCheckType(SyntaxLispElement cur, Map<String, SyntaxLispElement> env) {
        switch (cur.getType()) {

            case NOT_OR: {
                // Check NOT OR sub type
                ((NotOrElement) cur).getOrArgList()
                                    .forEach(sub -> checkNotOrArgTypes(sub, env, new HashSet<>()));
                inferAndCheckTypeOfSubs(cur, env);
                return cur;
            }
            case ALTERNATIVE:
            case ZERO_OR_MORE_GREEDY:
            case ZERO_OR_MORE:
            case ZERO_OR_ONE_GREEDY:
            case ZERO_OR_ONE:
            case ONE_OR_MORE_GREEDY:
            case ONE_OR_MORE:
            case SEQ_CONNECT: {
                inferAndCheckTypeOfSubs(cur, env);
                return cur;
            }

            case REPEAT_GREEDY:
            case REPEAT: {
                cur.setSub(2, inferAndCheckType(cur.getSub(2), env));
                checkOrThrow(SyntaxLispElementType.NUMBER == inferType(cur.getSub(0), env)
                                    || SyntaxLispElementType.NUMBER == inferType(cur.getSub(1), env),
                                      "REPEAT 前两个参数应为 NUMBER 类型!");
                NumberElement min = (NumberElement) cur.getSub(0);
                NumberElement max = (NumberElement) cur.getSub(1);
                checkOrThrow(!min.isInfinity() && min.getNumVal() >= 0,
                             "REPEAT 第一个参数 min match time 不能为 INF 并且应为非负整数!");
                checkOrThrow(max.getNumVal() >= 0,
                             "REPEAT 第二个参数 max match time 为非负整数!");
                checkOrThrow(max.isInfinity() || min.getNumVal() <= max.getNumVal(),
                             "REPEAT 第一个参数 min match time 不能大于 max match time!");
                return cur;
            }

            case SUBTRACT_SCOPE: {
                inferAndCheckTypeOfSubs(cur, env);
                checkOrThrow(isScopeType(inferType(cur.getSub(0), env)),
                                      "NOT_IN 第一个参数应为 SCOPE/NOT_IN 类型!");
                for (int i = 1; i < cur.getSubsSize(); i ++) {
                    checkOrThrow(isScopeType(inferType(cur.getSub(i), env))
                                         || SyntaxLispElementType.CHARACTER == inferType(cur.getSub(i), env),
                                 "NOT_IN 第二个之后参数应为 SCOPE/NOT_IN 或 CHARACTER 类型!");
                }
                return cur;
            }

            case SCOPE: {
                inferAndCheckTypeOfSubs(cur, env);
                checkOrThrow(SyntaxLispElementType.CHARACTER == inferType(cur.getSub(0), env)
                                    || SyntaxLispElementType.CHARACTER == inferType(cur.getSub(1), env),
                                      "SCOPE 前两个参数应为 CHARACTER 类型!");
                return cur;
            }

            case AMBIGUOUS_OR: {
                inferAndCheckTypeOfSubs(cur, env);
                for (SyntaxLispElement sub : cur.getSubElements()) {
                    SyntaxLispElementType subType = inferType(sub, env);
                    if (!isScopeType(subType) && SyntaxLispElementType.CHARACTER != subType) {
                        return new ListExpressionElement(SyntaxLispElementType.ALTERNATIVE, cur.getSubElements());
                    }
                }
                return new ListExpressionElement(SyntaxLispElementType.UNION_SCOPE, cur.getSubElements());
            }

            case IMP: {
//                inferAndCheckTypeOfSubs(cur, env);
                checkOrThrow(SyntaxLispElementType.STRING == cur.getSub(0).getType(),
                                      "IMPORT 参数应为 STRING 类型!");
                return cur;
            }

            case UNION_SCOPE:
            case STRING:
            case CHARACTER:
            case REF:
            case BASE: return cur;

            case NUMBER: throw new ParseException("NUMBER 类型只被用在 REPEAT 中!");

            default: throw new ParseException("未知类型" + cur.getType());
        }
    }

    private static void checkNotOrArgTypes(SyntaxLispElement cur,
                                           Map<String, SyntaxLispElement> env,
                                           Set<String> refSet) {

        switch (cur.getType()) {
            case AMBIGUOUS_OR:
            case ALTERNATIVE: {
                cur.getSubElements().forEach(sub -> checkNotOrArgTypes(sub, env, refSet));
                break;
            }
            case REF: {
                ReferencePair rp = trimReference((ReferenceElement) cur, env);
                if (refSet.contains(rp.getDefName())) {
                    throw new ParseException("There exist ref cycle while checking NOT-OR arg types");
                }
                refSet.add(rp.getDefName());
                checkNotOrArgTypes(rp.getElement(), env, refSet);
                refSet.remove(rp.getDefName());
                break;
            }
            default: {
                if (!SyntaxLispElementType.STRING.isTypeMatch(cur)
                    && !SyntaxLispElementType.CHARACTER.isTypeMatch(cur)
                    && !SyntaxLispElementType.BASE.isTypeMatch(cur)
                    && !isScopeType(cur.getType())) {
                    throw new ParseException("No support NOT-OR argument type: " + cur.getType());
                }
            }
        }
    }

    private static boolean isScopeType (SyntaxLispElementType type) {
        return SyntaxLispElementType.SCOPE == type
                || SyntaxLispElementType.SUBTRACT_SCOPE == type
                || SyntaxLispElementType.UNION_SCOPE == type
                || SyntaxLispElementType.IMP == type;
    }

    private static void inferAndCheckTypeOfSubs(SyntaxLispElement cur, Map<String, SyntaxLispElement> env) {
        for (int i = 0; i < cur.getSubsSize(); i ++) {
            cur.setSub(i, inferAndCheckType(cur.getSub(i), env));
        }
    }

    /**
     * 推断 Element 实际类型
     * @param cur 当前 Element
     * @param env environment
     * @return Element 实际类型
     */
    private static SyntaxLispElementType inferType(SyntaxLispElement cur, Map<String, SyntaxLispElement> env) {
        return SyntaxLispElementType.REF == cur.getType()
                ? trimReference((ReferenceElement) cur, env).getElement().getType()
                : cur.getType();
    }

    /**
     * 推断引用实际类型
     * @param startRef 引用 Element
     * @param env environment
     * @return 引用实际类型
     */
    private static ReferencePair trimReference(ReferenceElement startRef, Map<String, SyntaxLispElement> env) {

        String curDef = startRef.getVal();
        SyntaxLispElement curEle = env.get(curDef);

        List<String> refPath = new ArrayList<>();
        refPath.add(curDef);

        while (SyntaxLispElementType.REF == curEle.getType()
                && !refPath.contains(curEle.getVal())) {

            curDef = curEle.getVal();
            curEle = env.get(curDef);
            refPath.add(curDef);
        }

        if (SyntaxLispElementType.REF.isTypeMatch(curEle)) {
            throw new ParseException("存在循环引用: " + refPath);
        }
        return ReferencePair.builder().defName(curDef).element(curEle).build();
    }

    @Getter
    @Builder
    @AllArgsConstructor
    private static class ReferencePair {
        private final String defName;
        private final SyntaxLispElement element;
    }

    private static int parseCodePointFromString(Element rawEle) {
        if (ElementType.STRING == rawEle.getElementType()) {
            if (rawEle.getValue().length() == 1) {
                return rawEle.getValue().charAt(0);
            } else {
                throw new ParseException("Parse code point from element error: 只接受单个字符");
            }
        } else {
            throw new ParseException("Parse code point from element error: 只接受 STRING 类型的 Element");
        }
    }

    private static int parseHexDigit (Element hexEle) {
        if (StringUtils.isEmpty(hexEle.getValue())
                || hexEle.getValue().charAt(0) != '^') {
            throw new ParseException("输入的 HEX DIGIT Character '" + hexEle.getValue()
                                     + "' 不为空并且应为 '^HEX_DIGITS' 形式，例如： '^0EF8'");
        }
        String normalizeHexStr = hexEle.getValue().substring(1).toUpperCase();
        int res = 0;
        for (char hexBit : normalizeHexStr.toCharArray()) {
            if (hexBit >= '0' && hexBit <= '9') {
                res = (res << 4) + (hexBit - '0');
            } else if (hexBit >= 'A' && hexBit <= 'F') {
                res = (res << 4) + (hexBit - 'A' + 10);
            } else {
                throw new ParseException("非 HEX DIGIT Character");
            }
            if (res < 0) {
                throw new ParseException("HEX DIGIT 值过大溢出");
            }
        }
        return res;
    }

    private static int parseNumber (Element numberEle) {
        int res = 0;
        for (char decBit : numberEle.getValue().toCharArray()) {
            res = (res * 10) + SyntaxLispParseUtils.toDigitVal(decBit);
            if (res < 0) {
                throw new ParseException("NUMBER 值过大溢出");
            }
        }
        return res;
    }
}
